package sword.chapter10Trie;

/**
 * 实现前缀树
 *
 * 前缀树成员属性
 * 1. 前缀树数组TrieNode[]      children
 * 2. 是否是完整单词             isWord
 * 3. 数组下标从0-25，映射字母a-z
 *
 * @author K
 * @date 2021/12/15 09:17
 */
public class S62Trie {
    private TrieNode root;

    public S62Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (node.children[ch - 'a'] == null) {
                node.children[ch - 'a'] = new TrieNode();
            }
            node = node.children[ch - 'a'];
        }
        node.isWord = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (node.children[ch - 'a'] == null) {
                return false;
            }
            node = node.children[ch - 'a'];
        }
        return node.isWord;
    }

    public boolean startWith(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (node.children[ch - 'a'] == null) {
                return false;
            }
            node = node.children[ch - 'a'];
        }
        return true;
    }

    public static void main(String[] args) {
        String a = "goodbye";
        String b = "boy";
        String c = "body";
        String d = "baby";

        S62Trie trie = new S62Trie();
        trie.insert(a);
        trie.insert(b);
        trie.insert(c);
        trie.insert(d);

        boolean result = trie.search("good");
        boolean result2 = trie.startWith("good");
        System.out.println();
    }
}

class TrieNode {
    TrieNode children[];
    boolean isWord;

    public TrieNode() {
        children = new TrieNode[26];
    }
}